1. Field of the Invention
The present invention generally relates to the detection of bit values in a bit string. More specifically, the invention relates to identifying and generating the location of a leading or trailing one or zero in a string of binary numbers.
2. Background of the Invention
In the field of computer science and binary number processing, there are many occasions in which it is necessary to locate the leading or trailing non-zero bit in a string of bits. For example, the normalization procedure in floating point processors sometimes involves a leftward shift of a string of bits up to the first significant bit. This requires some prior knowledge of the position of the most significant non-zero bit thereby allowing non-significant zeroes to be discarded while retaining relevant data. Similarly, in right shift or truncation scenarios, processors need to keep track of the location of the least significant non-zero bit to maintain data integrity.
Another example of a need to determine the location of low order non-zero bits is in “sticky bit” calculations. These calculations require knowledge of the position of non-zero bits at the least significant end of the bit stream. In floating point processors, data bit streams commonly use guard and round bits, which are two bits of precision that are used in calculations. The sticky bit is beyond (less significant than) the guard and round bits and provides an indication of the value of lesser significant bits that are not kept. If a non-zero value is shifted into the sticky bit position, that sticky bit remains a one (“sticks” at one), despite further shifts.
Other examples of when a leading one must be identified certainly exist. For instance, in variable length coding, long strings of ones or zeros may be eliminated from binary data to compress the size of digital transmissions. These long strings of continuous bits are replaced by a marker that indicates the value and quantity of bits being replaced. Before replacing the string of bits, the coding scheme must determine the number of continuous bits in a given string. This can be done by searching for the first bit change in a string of bits. By determining the location where a string of continuous ones or zeros ends, this may eliminate the need to count the individual bits until a bit change is encountered.
Conventional methods of locating a leading bit value in a string of bits are cumbersome and time-consuming. The most trivial solution (as alluded to above) involves shifting bits out of a register one by one until a bit change is located. This brute force method of locating a leading one or zero quickly becomes impractical in scanning large strings of bits for leading ones and zeros.
Another conventional method involves parallel, cascaded comparisons of adjacent bits. As an example of the simplest form of searching for a leading one, this method compares adjacent pairs of bits and if the more significant bit is a one, the less significant bit is forced to zero. Otherwise, if the more significant bit is a zero, the less significant bit value is retained. In the next cascaded step, the previously checked pairs of bits are grouped together and compared in much the same way, i.e., leaving the most significant one intact and forcing all others to zero. This process is repeated until a single bit has a value of one. The position of this bit may then be encoded into a binary representation of the bit position.
Because of its parallel nature, this method proves to be faster than the first conventional method provided above. In practice, adjacent bits may be compared in groups larger than pairs of bits using encoders. Implementation of this method may consist of a large cascading structure of static encoders and, for a 64-bit number, can produce the encoded leading bit position with a latency of roughly one computer clock cycle.
Despite the effectiveness of this conventional technique, processing speeds and computer performance could be improved if the time required to produce the location of a leading binary value is decreased. It is desirable, therefore, to provide a faster and more compact means of locating and generating an encoded representation of a leading binary value. The novel technique would advantageously decrease the amount of time required to perform floating point operations in a computer processor.